package algs4.ds;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedQueue<E> extends Queue<E>
{
    /* Inner Class */
    private class QueueIterator implements Iterator<E>
    {
        private Node<E> link = head.next;

        public boolean hasNext() { return link != tail;                         }
        public E       next()    { E e = link.data; link = link.next; return e; }
    }

    /* Fields */
    private Node<E> head;
    private Node<E> tail;
    private int     size;

    /* Constructors */
    public LinkedQueue() {
        tail = new Node<>();
        head = new Node<>(null, tail);
        size = 0;
    }

    /* Instance Methods */
    public boolean     isEmpty()  { return head.next == tail;  }
    public int         size()     { return size;               }
    public Iterator<E> iterator() { return new QueueIterator(); }

    public void enqueue(E e) {
        tail.data = e;
        tail.next = new Node<>();

        // update
        tail = tail.next;
        size++;
    }

    public E dequeue() throws NoSuchElementException {
        // if queue is empty, then throw exception
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");

        // retrieve element
        E e = head.next.data;

        // update
        head.next = head.next.next;
        size--;

        return e;
    }

    public E peek() throws NoSuchElementException {
        // if queue is empty, then throw exception
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");

        return head.next.data;
    }

    /* Main Test */
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedQueue<>();

        for (int i = 1; i < 100; i++) {
            if (i % 3 == 0) queue.dequeue();
            else            queue.enqueue(i);
        }

        for (int i : queue)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("size = " + queue.size());
    }
}
